

// Definition for singly-linked list.

  class ListNode {

      int val;

      ListNode next;

      ListNode(int x) {

          val = x;

          next = null;

      }

  }

public class Solution {

    public static void main (String[] args) {
	ListNode[] list = new ListNode[args.length];
	for (int i = 0; i < args.length; ++i)
		list[i] = new ListNode(Integer.parseInt(args[i]));
	for (int i = 0; i < args.length - 1; ++i)
		list[i].next = list[i+1];
	
	Solution s = new Solution();
	ListNode ln = s.sortList(list[0]);
	
	for (ListNode l = ln; l != null; l = l.next)
		System.out.print(l.val + " ");
	System.out.println();
    }

    public ListNode sortList(ListNode head) {

        if (head == null || head.next == null)

            return head;

            

        return sortListHelper(head);

    }

   

    private ListNode sortListHelper(ListNode head) {

        if (head == null || head.next == null)

            return head;

            

        ListNode pre = null, cur = head, fast = head;

        while(cur != null && fast != null && fast.next != null) {

            pre = cur;

            cur = cur.next;

            fast = fast.next.next;

        }

        pre.next = null;

        

        ListNode n1 = sortListHelper(head);

        ListNode n2 = sortListHelper(cur);

        ListNode n = merge(n1, n2);

        return n;

    }

    

    private ListNode merge(ListNode n1, ListNode n2) {

        //insert all n2 nodes to the list of n1

        

        ListNode pre = null, cur = n1;

        ListNode cur2 = n2;

        while (cur2 != null) {

            //get current node in n2 list as l

            ListNode l = cur2;

            cur2 = cur2.next;

            

            while (cur != null && l.val >= cur.val) {

                pre = cur;

                cur = cur.next;

            }


	    if (cur == null) {
	    	l.next = null;
		pre.next = l;
		cur = l;
		continue;
	    }           

            // we either reach the end of the list or have l.val < cur.val satisfied.

            // insert l before cur and after pre

            if (pre == null) {

                    l.next = cur;

                    n1 = l;

		    pre = l;
                } else {

                    l.next = cur;

                    pre.next = l;

		    pre = pre.next;
                }

        }

        

        return n1;

    }

    

}
